BZOJ 1927 星际竞速

Description

10 年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一, 夺得这个项目的冠军无疑是很多人的梦想,来自杰森座 α星的悠悠也是其中之一。 赛车大赛的赛场由 N 颗行星和M条双向星际航路构成,其中每颗行星都有 一个不同的引力值。大赛要求车手们从一颗与这 N 颗行星之间没有任何航路的 天体出发,访问这 N 颗行星每颗恰好一次,首先完成这一目标的人获得胜利。 由于赛制非常开放,很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾 驶的赛车名为超能电驴,这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作 为最高科技的产物,超能电驴有两种移动模式:高速航行模式和能力爆发模式。 在高速航行模式下,超能电驴会展开反物质引擎,以数倍于光速的速度沿星际航 路高速航行。在能力爆发模式下,超能电驴脱离时空的束缚,使用超能力进行空 间跳跃——在经过一段时间的定位之后,它能瞬间移动到任意一个行星。 天不遂人愿,在比赛的前一天,超能电驴在一场离子风暴中不幸受损,机能 出现了一些障碍:在使用高速航行模式的时候,只能由每个星球飞往引力比它大 的星球,否则赛车就会发生爆炸。 尽管心爱的赛车出了问题,但是悠悠仍然坚信自己可以取得胜利。他找到了 全银河最聪明的贤者——你,请你为他安排一条比赛的方案,使得他能够用最少 的时间完成比赛。

Input

第一行是两个正整数 N, M。 第二行 N 个数 A1~AN, 其中Ai表示使用能力爆发模式到达行星 i 所需的定位 时间。 接下来 M行,每行 3个正整数ui, vi, wi,表示在编号为 ui和vi的行星之间存 在一条需要航行wi时间的星际航路。 输入数据已经按引力值排序,也就是编号小的行星引力值一定小,且不会有 两颗行星引力值相同。

Output

仅包含一个正整数,表示完成比赛所需的最少时间。

Sample Input

3 3

1 100 100

2 1 10

1 3 1

2 3 1

Sample Output

12

Hint

说明:先使用能力爆发模式到行星 1,花费时间 1。
然后切换到高速航行模式,航行到行星 2,花费时间10。
之后继续航行到行星 3完成比赛,花费时间 1。
虽然看起来从行星 1到行星3再到行星 2更优,但我们却不能那样做,因为
那会导致超能电驴爆炸。

对于 30%的数据 N≤20,M≤50;
对于 70%的数据 N≤200,M≤4000;
对于100%的数据N≤800, M≤15000。输入数据中的任何数都不会超过106

输入数据保证任意两颗行星之间至多存在一条航道,且不会存在某颗行星到
自己的航道。

Solution

用费用流跑下界
使用爆发模式的次数应该和答案是单峰的
每次更新ans就可以了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>

#define maxn 1600+5
#define maxm 35000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct sides{
int u,v,c,w;
int next;
}s[maxm];

queue<int> q;
ll dis[maxn],ans,res=LLONG_MAX;
int par[maxn],inq[maxn],a[maxn];
int first[maxn],ind;
int n,m,S,T;

void insert(int u,int v,int c,int w)
{

s[ind]=(sides){u,v,c,w,first[u]},first[u]=ind++;
s[ind]=(sides){v,u,0,-w,first[v]},first[v]=ind++;
}

void costflow()
{

while( true ){
for(int i=S;i<=T;i++) dis[i]=LLONG_MAX/2;
dis[S]=0,q.push(S);
while( !q.empty() ){
int sd=q.front();q.pop();
inq[sd]=0;
for(int i=first[sd];i!=-1;i=s[i].next)
if( s[i].c>0 && dis[s[i].v]>dis[sd]+s[i].w ){
dis[s[i].v]=dis[sd]+s[i].w;
par[s[i].v]=i;
if( !inq[s[i].v] ){
inq[s[i].v]=1;
q.push(s[i].v);
}
}
}
if( dis[T]==LLONG_MAX/2 ) break;
int t=T,flow=INT_MAX;
while( S!=t ){
flow=min(flow,s[par[t]].c);
t=s[par[t]].u;
}
t=T;
while( S!=t ){
s[par[t]].c-=flow,s[par[t]^1].c+=flow;
ans+=(ll)flow*s[par[t]].w,t=s[par[t]].u;
}
if( res>ans-(ll)n*(INT_MIN+1) )
res=ans-(ll)n*(INT_MIN+1);
else break;
}
}

int main()
{

#ifndef ONLINE_JUDGE
freopen("1927.in","r",stdin);
freopen("1927.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
set(first,-1);
S=0,T=2*n+1;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
insert(S,i,1,a[i]);
insert(i+n,T,1,0);
insert(i,i+n,1,(INT_MIN+1));
}
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
if( u>v ) swap(u,v);
insert(u+n,v,1,w);
}
costflow();
printf("%lld",res);
return 0;
}